Day26 Leetcode Array系列---- Minimum Size Subarray Sum

本次題目 Minimum Size Subarray Sum by js

這題是要在大陣列中找加總結果是目標值的最小子陣列的長度，如果要求的數字是 10 ，就要去找大陣列中哪些段落是符合的，找出最小長度

Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length under the problem constraint.

思考路線 1

1. 雙迴圈取值，把所有可能的片段都跑過一輪
2. 要計算加總，可以用 reduce
3. 要比較每一次取到的片段長度，保留最小的結果

Coding Time

這裡用雙迴圈得到的 i j 當作範圍去取原陣列的範圍 (slice) ，取出範圍後計算陣列元素總和 (reduce) ，計算出的總和與目標值做比較，如果大於或等於則紀錄該陣列長度

// input:
 s = 7, nums = [2,3,1,2,4,3]
output =  2
// Explanation: the subarray [4,3] has the minimal length under the problem constraint.

function minimumSize( s, ary ){
  let length = 0
  for( let i = 0 ; i < ary.length; i++){
    for(let j = i; j< ary.length; j++){
      let sum = ary.slice(i,j+1).reduce((acc,num)=>{ return acc+num },0)
      if(sum >= s){
        length = ary.slice(i,j+1).length
      }
    }
  }
  return length
}

function expect(a,b){
  console.log( a == b )
}

expect( minimumSize( s , nums ) , output )

思考路線 ２

1. 單迴圈
2. 用動態規劃的方式，做出 start end 兩個指標
3. 迴圈終止就是兩個指標碰頭
4. 陣列長度與陣列加總與思考路線 1 一樣
5. 移動指針的依據就比較以兩個指針為索引取出的值，哪邊小就哪邊往中央推進
6. 如果以兩個指針為索引取出的值一樣大，就比這兩個元素往中央一格的值大小，哪邊小就朝中央推進

Coding Time

// input:
 s = 7, nums = [2,3,1,2,4,3]
output =  2
// Explanation: the subarray [4,3] has the minimal length under the problem constraint.

function minimumSize( s, ary ){
  let length = 0
  let start = 0
  let end = ary.length-1
  while( start < end ){                //同上作法
    let sum = ary.slice(start,end+1).reduce((acc,num)=>{ return acc+num },0 )
    
    if(sum >= s){                      //同上作法
      length = ary.slice( start , end + 1 ).length
    }

    if(ary[start] < ary[end]){   // 比較取出的值大小
      start += 1
    }else if (ary[start] > ary[end] ){
      end -= 1
    }else{   // 如果取出的值一樣大就比往中間一格的值大小
      
      if( ary[start+1] < ary[end-1] ){
        start +=1
      }else{
        end -=1
      }

    }
  }
  return length
}

function expect(a,b){
  console.log( a == b )
}

expect( minimumSize( s , nums ) , output )

今天到此為止，有任何問題請在下方留言或透過email、GitHub聯絡我，感謝閱讀

Daily kitty